package my.graph;

import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * 图的顶层抽象父类
 *
 * @author AJun
 * @date 2020/11/09
 */
public abstract class Graph<V, E> {

    protected WeightManager<E> weightManager;

    public Graph() {

    }

    public Graph(WeightManager<E> weightManager) {
        this.weightManager = weightManager;
    }

    /**
     * 打印图
     */
    public abstract void print();

    /**
     * 获取边的数量
     *
     * @return 边数量
     */
    public abstract int edgesSize();

    /**
     * 获取顶点的数量
     *
     * @return 顶点数量
     */
    public abstract int verticesSize();

    /**
     * 添加一个顶点
     *
     * @param v 顶点值
     */
    public abstract void addVertex(V v);

    /**
     * 添加一条边，附加权值
     *
     * @param from 起点
     * @param to   终点
     */
    public abstract void addEdge(V from, V to);

    /**
     * 添加一条边，附加权值
     *
     * @param from   起点
     * @param to     终点
     * @param weight 权值
     */
    public abstract void addEdge(V from, V to, E weight);

    /**
     * 删除一个顶点
     *
     * @param v 顶点值
     */
    public abstract void removeVertex(V v);

    /**
     * 删除一条边
     *
     * @param from 起点
     * @param to   终点
     */
    public abstract void removeEdge(V from, V to);

    /**
     * 广度优先搜索
     *
     * @param begin 起点
     */
    public abstract void bfs(V begin, VertexVisitor<V> visitor);

    /**
     * 深度优先搜索
     *
     * @param begin 起点
     */
    public abstract void dfs(V begin, VertexVisitor<V> visitor);

    /**
     * 拓扑排序(必须是有向无环图)
     *
     * @return List 排序后的集合
     */
    public abstract List<V> topologicalSort();

    /**
     * 最小生成树
     *
     * @return 最小生成树的边
     */
    public abstract Set<EdgeInfo<V, E>> mst();

    /**
     * 最短路径
     *
     * @param begin 开始节点
     * @return Map 最短路径及其路径上的边信息
     */
    public abstract Map<V, PathInfo<V, E>> shortestPath(V begin);

    public abstract Map<V, Map<V, PathInfo<V, E>>> shortestPath();

    /**
     * 遍历的访问器
     */
    public interface VertexVisitor<V> {
        boolean visit(V v);
    }

    /**
     * 权重管理者
     */
    public interface WeightManager<E> {
        int compare(E w1, E w2);

        E add(E w1, E w2);

        E zero();
    }

    /**
     * 边的信息
     */
    public static class EdgeInfo<V, E> {
        private V from;
        private V to;
        private E weight;

        public EdgeInfo(V from, V to, E weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        public V getFrom() {
            return from;
        }

        public void setFrom(V from) {
            this.from = from;
        }

        public V getTo() {
            return to;
        }

        public void setTo(V to) {
            this.to = to;
        }

        public E getWeight() {
            return weight;
        }

        public void setWeight(E weight) {
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "EdgeInfo{" +
                "from=" + from +
                ", to=" + to +
                ", weight=" + weight +
                '}';
        }
    }

    /**
     * 路径信息
     */
    public static class PathInfo<V, E> {
        protected E weight;
        protected List<EdgeInfo<V, E>> edgeInfos = new LinkedList<>();

        public PathInfo() {

        }

        public PathInfo(E weight) {
            this.weight = weight;
        }

        public E getWeight() {
            return weight;
        }

        public void setWeight(E weight) {
            this.weight = weight;
        }

        public List<EdgeInfo<V, E>> getEdgeInfos() {
            return edgeInfos;
        }

        public void setEdgeInfos(List<EdgeInfo<V, E>> edgeInfos) {
            this.edgeInfos = edgeInfos;
        }

        @Override
        public String toString() {
            return "PathInfo{" +
                "weight=" + weight +
                ", edgeInfos=" + edgeInfos +
                '}';
        }
    }

}
